package day_2022_7_to_8.day48;
import java.util.*;
/**
 * @author haomin
 * @date 2022/08/27 21:33
 **/
public class Day42_1_Num662_WidthOfBinaryTree {
    class Solution1 {
        public int widthOfBinaryTree(TreeNode root) {
            if(root == null) return 0;
            Map<TreeNode, Integer> map = new HashMap<>();
            Queue<TreeNode> queue = new LinkedList<>();
            int max = 0;
            map.put(root, 1);
            queue.offer(root);
            while(!queue.isEmpty()){
                int start = map.get(queue.peek());
                int end = 0;
                int size = queue.size();
                for(int i = 0; i < size; ++i){
                    TreeNode cur = queue.poll();
                    end = map.get(cur);
                    if(cur.left != null){
                        map.put(cur.left, end * 2);
                        queue.offer(cur.left);
                    }
                    if(cur.right != null){
                        map.put(cur.right, end * 2 + 1);
                        queue.offer(cur.right);
                    }
                }
                max = Math.max(max, end - start + 1);
            }
            return max;
        }
    }
    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            Queue<NodeWithNum> queue = new LinkedList<>();
            queue.offer(new NodeWithNum(root, 1));
            int maxWide = 0;
            while(!queue.isEmpty()){
                int size = queue.size();
                int l = 0, r = 0;
                for(int i = 0; i < size; ++i){
                    NodeWithNum cur = queue.poll();
                    if(i == 0) l = cur.num;
                    if(i == size-1) r = cur.num;
                    if(cur.node.left != null){
                        queue.offer(new NodeWithNum(cur.node.left, cur.num * 2));
                    }
                    if(cur.node.right != null){
                        queue.offer(new NodeWithNum(cur.node.right, cur.num * 2 + 1));
                    }
                }
                maxWide = Math.max(maxWide,r-l+1);
            }
            return maxWide;
        }
        public class NodeWithNum {
            TreeNode node;
            int num;
            NodeWithNum(TreeNode node, int num){
                this.node = node;
                this.num = num;
            }
        }
    }
    class Solution3 {
        Map<Integer, Integer> map = new HashMap<>();
        int ans;
        public int widthOfBinaryTree(TreeNode root) {
            dfs(root, 1, 0);
            return ans;
        }
        private void dfs(TreeNode root, int index, int depth){
            if(root == null) return;
            if(!map.containsKey(depth)) map.put(depth, index);
            ans = Math.max(ans, index - map.get(index) + 1);
            index = index - map.get(depth) + 1;
            dfs(root.left, index * 2, depth + 1);
            dfs(root.right, index * 2 + 1, depth+1);
        }
    }
}